#include <iostream>
#include <vector>
#include<limits.h>
using namespace std;

/*
 *
 *Prioty queues
 *
 *
*/

int SimapleArray[]={15,13,9,5,12,8,7,4,0,6,2,1};

class PrintInt
	{
	public:
		void operator()(int elem) const 
		{
			cout << elem<<' ';
		}
	};
//MAX-HEAPIFY by recursion
//i from one
//and item
void max_heapify(vector<int> &vec,int i)
{
	int l=2*i;
	int r=2*i+1;
	int largest;
	if(l<=vec.size()&&(vec[l-1]>vec[i-1]))
		largest=l;
	else {
		largest=i;
	}
	if(r<=vec.size()&&(vec[r-1]>vec[largest-1]))
		largest=r;
	if(largest!=i)
	{
		swap(vec[i-1],vec[largest-1]);
		max_heapify(vec,largest);
	}
	
}

void build_max_heap(vector<int> &vec)
{
	for(int i=vec.size()/2;i>0;i--)
	{
		max_heapify(vec,i);
	}
}

int heap_extract_max(vector<int>& vec)
{
	if(vec.size()<1)
	{
		cout<<"heap underflow\n";
		return -1;
	}
	int max=vec[0];
	vec[0]=vec[vec.size()-1];
	vec.pop_back();
	max_heapify(vec,1);
	return max;
}
//MAX-HEAPIFY by recursion
//i from one
void heap_increase_key(vector<int>& vec,int i, int key)
{
	if(key<vec[i-1])
	{
		cout<<"new key is smaller tahn current key\n";
		return;
	}
	for(vec[i-1]=key;i>0&&vec[i/2-1]<vec[i-1];i=i/2)
		swap(vec[i-1],vec[i/2-1]);
}

void max_heap_insert(vector<int>& vec,int key)
{
	int size=vec.size();
	vec.resize(++size,numeric_limits<int>::min());
	heap_increase_key(vec,size,key);
}

int main (int argc, char * const argv[]) {
    // insert code here...
	vector<int> A;
	int size=sizeof(SimapleArray)/sizeof(int);
	for(int i=0;i<size;i++)
	{
		A.push_back(SimapleArray[i]);
	}
    cout << "Array before sorting\n";
	for_each(A.begin(), A.end(), PrintInt());
	cout<<endl;
	/*
	cout<<"The heap extract max is "<<heap_extract_max(A)<<endl;
	 */
	max_heap_insert(A,10);
	cout << "Array afert sorting\n";
	for_each(A.begin(), A.end(), PrintInt());
	
	cout<<endl;
	
    return 0;
}
